package com.gxc.integer;

import java.util.function.ToIntFunction;

/**
 * 69. x 的平方根
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 *
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 *
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 */
public class MySqrt {

    public static void main(String[] args) {
        System.out.println(Math.log(65536));

        System.out.println(handle(8));
    }

    public static int handle(int x) {
        if (x==0 || x==1) return x;
        int base = 1;
        while (x > base && base<46340) {
            base = base * 2;
        }
        if (base>46340) base = 46340;
        int l = 0;
        int r = base;
        int m = 0;
        long sum = 0;
        while (l <= r) {
            m = (l+r)/2;
            sum = (long) m * m;
            if (sum == x) {
                return m;
            } else if (sum < x){
                l = m+1;
            } else {
                r = m-1;
            }
        }
        return sum > x ?m-1:m;
    }

    class Solution {
        public int mySqrt(int x) {
            if (x == 0) {
                return 0;
            }
            int ans = (int) Math.exp(0.5 * Math.log(x));
            return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
        }
    }

    class Solution2 {
        public int mySqrt(int x) {
            int l = 0, r = x, ans = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if ((long) mid * mid <= x) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return ans;
        }
    }


}
